package LeetCode._02算法基础.day13动态规划;

import 题组.Solution;

/**
 * @author 挚爱之夕
 * @version 中等
 * @implSpec 给你一个非负整数数组nums ，你最初位于数组的第一个位置。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 * 假设你总是可以到达数组的最后一个位置。
 *
 * 输入: nums = [2,3,1,1,4]
 * 输出: 2
 * 解释: 跳到最后一个位置的最小跳跃数是 2。
 * 从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。
 * @since 2022 - 09 - 09 - 16:30
 */
public class _45跳跃游戏2 {
    public static void main(String[] args) {
        int[] nums = {2,3,1,1,4};
        int res = jump1(nums);
        System.out.println(res);
    }
    //by me
    public static int jump(int[] nums) {
        if(nums.length == 1)
            return 0;
        if(nums.length == 2)
            return 1;
        //找出到达每个位置的最小跳跃次数
        int[] minCnt = new int[nums.length];
        minCnt[0] = 0;
        minCnt[1] = 1;
        for(int i = 2; i < nums.length; i++){
            minCnt[i] = Integer.MAX_VALUE;
            //当前位置是从前面跳过来的
            for(int j = 0; j < i; j++){
                if(j + nums[j] >= i){   //从 j 可到达 i 位置
                    minCnt[i] = Math.min(minCnt[i], minCnt[j] + 1); //取最小跳跃次数
                }
            }
        }
        return minCnt[nums.length - 1];
    }
    //官方思想
    public static int jump1(int[] nums) {
        int length = nums.length;
        //上次跳跃时最大的可达索引
        int end = 0;
        //目前最大可达索引
        int maxPosition = 0;
        //跳跃次数
        int steps = 0;
        /*
        访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。
        如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，
        因此我们不必访问最后一个元素。
         */
        for (int i = 0; i < length - 1; i++) {
            //记录当前可达的最大索引
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) { //跳跃
                //更新这次跳跃最大可达索引（可能并不是从上个跳跃点可达，而是上个跳跃点前的某个点）
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
}
